﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode.CodeDay
{
    /**可以使用动态规划计算出界的路径数。
            动态规划的状态由移动次数、行和列决定，定义 \textit{dp
            }
            [i][j][k]dp[i][j][k] 表示球移动 ii 次之后位于坐标 (j, k)(j, k) 的路径数量。当 i=0i=0 时，球一定位于起始坐标 (\textit{startRow}, \textit
            { startColumn})(startRow, startColumn)，因此动态规划的边界情况是：\textit
            { dp}
            [0] [\textit{startRow}][\textit{startColumn}]= 1dp[0][startRow][startColumn] = 1，当(j, k) \ne(\textit{ startRow}, \textit
            { startColumn})(j, k)
             = (startRow, startColumn) 时有 \textit
            { dp}
            [0][j][k]= 0dp[0][j][k] = 0。

            如果球移动了 ii 次之后位于坐标 (j, k)(j, k)，且 i < \textit{ maxMove }
            i < maxMove，0 \le j<m0≤j<m，0 \le k < n0≤k<n，则移动第 i+1i+1 次之后，球一定位于和坐标 (j, k)(j, k) 相邻的一个坐标，记为 (j', k')(j
            ′,k  ′
             )。

            当 0 \le j' < m0≤j 
            ′
             <m 且 0 \le k' < n0≤k 
            ′
             <n 时，球在移动 i+1i+1 次之后没有出界，将 \textit{dp}[i][j][k]dp[i][j][k] 的值加到 \textit
            { dp}
            [i+1][j'][k']dp[i + 1][j 
            ′
             ][k 
            ′
             ]；

            否则，球在第 i+1i+1 次移动之后出界，将 \textit{dp}[i][j][k]dp[i][j][k] 的值加到出界的路径数。

            由于最多可以移动的次数是 \textit
            { maxMove}
            maxMove，因此遍历 0 \le i < \textit{ maxMove }
            0≤i < maxMove，根据 \textit
            { dp}
            [i][][]dp[i][][] 计算 \textit
            { dp}
            [i+1][][]dp[i + 1][][] 的值以及出界的路径数，即可得到最多移动 \textit
            { maxMove}
            maxMove 次的情况下的出界的路径数。

            根据上述思路，可以得到时间复杂度和空间复杂度都是 O(\textit{maxMove} \times m \times n)O(maxMove×m×n) 的实现

            **/
    public partial class Code
    {
      
            public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn)
            {
                const int MOD = 1000000007;
                int[][] directions = new int[][] {
            new int[]{-1, 0},
            new int[]{1, 0},
            new int[]{0, -1},
            new int[]{0, 1}
        };
                int outCounts = 0;
                int[,,] dp = new int[maxMove + 1, m, n];
                dp[0, startRow, startColumn] = 1;
                for (int i = 0; i < maxMove; i++)
                {
                    for (int j = 0; j < m; j++)
                    {
                        for (int k = 0; k < n; k++)
                        {
                            int count = dp[i, j, k];
                            if (count > 0)
                            {
                                foreach (int[] direction in directions)
                                {
                                    int j1 = j + direction[0], k1 = k + direction[1];
                                    if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n)
                                    {
                                        dp[i + 1, j1, k1] = (dp[i + 1, j1, k1] + count) % MOD;
                                    }
                                    else
                                    {
                                        outCounts = (outCounts + count) % MOD;
                                    }
                                }
                            }
                        }
                    }
                }
                return outCounts;
            }
        }
}
